The invention relates generally to a method and apparatus for generating halftone reproductions, and in particular, to a method and apparatus for generating digital angled halftone screens for reducing moire effects in multicolor halftone reproduction.
Digital halftoning generally refers to a non-continuous (or digital) printing process for creating the illusion of continuous tone images from an arrangement binary picture elements (pixels). In its most rudimentary form, halftoning includes optically scanning, point to point, an original image whereby an electrical signal indicative of the reflected light from the original is derived and then compared with a fixed threshold signal level. Typically, if the scanned sample is less than the threshold value, a black pixel is recorded at a corresponding point on an exposure medium. However, if the reflected light from the scanned pixel is greater than the threshold value a white pixel is recorded at the corresponding point. This process is repeated until the original has been completely scanned. While a fixed threshold preserves much of the detail of the scanned image, variations of grey which fluctuate entirely above or below a selected fixed threshold are obliterated.
The threshold signal is frequently referred to as a screen signal. The term "screen signal" derives from conventional photographic halftoning where gray levels are achieved by projecting the image of an original onto a sheet of high contrast lithographic film through an out-of-focus screen. As with a screen in the photographic process, the threshold signal of a digital system is effectively superimposed onto the continuous tone original.
In order to digitally simulate the visual effect achieved through traditional photographic halftoning techniques, prior art systems vary the screen signal level. Varying the screen signal, sometimes referred to as spatial dithering, redistributes fixed quantization error in such a way as to render it less visible. The screen signal may be varied randomly or in an ordered fashion. Many well known algorithms exist for generating screen signals. These algorithms may be divided into two categories: clustered-dot ordered dither and dispersed-dot ordered dither.
A "dot", for purposes of digital halftone, is a small area in an output medium containing a group of pixels. Since the human eye performs spatial integration when viewing objects from a distance, a gray level can be simulated by causing a subset of pixels contained in a plurality of dots to be "on" (where "on" denotes a black pixel) and "off" (which denotes a white pixel). Moreover, differing gray levels can be achieved by varying the ratio of "on" pixels to "off" pixels. For example, an illusion of middle gray may be created by causing one half of the pixels in a group of dots to be "on". The object of clustered-dot techniques is to group "on" pixels together, and the object of dispersed-dot techniques is to disperse "on" pixels as homogeneously as possible throughout the dot.
It is well known to those practiced in the art of halftone reproduction that screen signals may be stored in digital memory as threshold arrays. Typically, each element in the threshold array represents a dither threshold value and is mapped through a Cartesian coordinate system to pixel locations on the continuous tone original and on the output medium. A "screen dot" is generally defined as comprising a group of elements of a threshold array containing the screen signal information corresponding to the group of pixels contained in a particular dot on the output medium. Ordered dither algorithms generate binary halftone images by comparing reflected light from pixels of an original continuous tone image to corresponding threshold values stored as elements in the threshold array.
It would require a very large memory to store the threshold array for a screen large enough to be superimposed on an entire original image. Therefore, it is not uncommon for screen signals to be designed as periodic functions. If the screen signal is repetitive, then only one period of the threshold array need be stored. The single repetition of the screen signal stored in a threshold array is sometimes referred to as a screen "tile", "brick" or "square". Threshold values stored in this fashion are usually mapped to pixel locations on the continuous tone original through a Cartesian coordinate system, modulo the dimensions of the repeating array.
Generally, the screen tile must contain at least as many elements as the smallest screen dot. Since the number of gray levels which can be represented increases with the size of the repeating area, some prior art systems utilize larger tiles containing a plurality of screen dots. However, if a screen tile is made excessively large unwanted lower spatial frequency components may be introduced.
It is well known that images resulting from conventional photographic halftoning of monochromatic originals "look better" if the screen is oriented at a 45 degree angle. This follows from a lack of symmetry in the frequency response of the human visual system. Sharp cusps occur at the horizontal and vertical orientations. Therefore, it is common practice in digital halftoning of monochromatic images to rotate the threshold array or screen 45 degrees from the horizontal. In the case where only one period of the screen signal is stored, the rotation is generally accomplished by rotating a single tile through 45 degrees and then taking into consideration the angle of rotation when mapping subsequent tiles to pixel locations on the output medium. Low spatial frequency patterning is typically introduced by traditional methods of creating and combining tiles.
Digital halftoning techniques are commonly applied to color reproduction. Typically, a continuous tone color original is optoelectronically sampled pixel by pixel much in the same way as a monochromatic original. Three primary color signals are obtained for each pixel from which color separation signals magenta, cyan, yellow, and black (key) are derived. The sampled color separation signals are then individually compared to screen threshold values stored in corresponding threshold arrays. As in the monochromatic example, if a color separation signal is greater than the corresponding threshold value, an "on" pixel is recorded for that color separation, otherwise an "off" pixel is recorded.
Whenever two periodic structures of nearly the same period are superimposed, a moire pattern results. Such patterns occur in halftone color reproduction due to the interaction of the dot arrangements comprising the component colors. It is generally accepted that moire patterns are minimized through judiciously selecting the dot shapes and the angles of rotation for the halftone screens for each color separation. As noted above, a 45 degree rotation from horizontal is typically selected for black. Angles of 15 and 75 degrees are generally used for the cyan and magenta separations respectively. Angles of zero, 30 and 60 degrees have been used for the yellow separation. It is well known to those skilled in the art of halftone reproduction that any inaccuracies in the screen angles substantially increase the observable moire patterning.
It is impossible to produce error free exact angled screens for angles of 15 and 75 degrees on a discrete raster recorder. This is a consequence of the tangents of both angles being irrational. However, it is well known that such errors can be rendered insignificant by creating a threshold array with an arbitrarily large number of elements. Nevertheless, enthusiasm for exactness is restrained by the increased cost associated with digital memories large enough to store the requisite threshold arrays. Threshold array size is also limited by the complexity of manually assigning pixels to each screen dot in addition to combining the screen dots to form the requisite screen tiles.
It is therefore an object of the present invention to provide an automated method for constructing screen dots so that threshold arrays containing large numbers of pixels can be used to more closely approximate ideal color separation screen angles.
It is a further object of the invention to assign pixels to screen dots to minimize moire patterning resulting from interaction of the dot arrangements comprising each of the color components.
It is also an object of the invention to provide an automated method for creating rotated screen tiles to minimize low spatial frequency patterning.